-- Linked-list Processing --

list.length $ 0 #
list.length (., .tail) .len1 :-
	io.order .len1:. (
		(sum .len 1 .len1, .len >= 0),
		list.length .tail .len
	) #

list.member (.element, .) .element #
list.member (., .tail) .element :-
	list.member .tail .element #

	-- Removes any occurrence
list.remove (.element, .tail) .element (.tail) #
list.remove (.head, .tail) .element (.head, .tail1) :-
	list.remove .tail .element .tail1 #

	-- Concatenate two lists
list.append $ .list .list #
list.append (.head, .tail) .right (.head, .remain) :-
	list.append .tail .right .remain #

	-- Concatenate list of lists (lol!!!)
lists.append $ $ #
lists.append (.head, .tail) .list :-
	list.append .head .remains .list,
	not (.head = $), -- If you want lol from list, and hate to stuck
	lists.append .tail .remains #

	-- Reverses a list, accelerated using difference list
list.reverse .l1 .l2 :-
	reverseToDiflist .l1 .x:.xt,
	list.fromDiflist .l2 .x:.xt #

reverseToDiflist $ .x:.x #
reverseToDiflist (.head, .tail) .x:.xt :-
	reverseToDiflist .tail .x:(.head, .xt) #

list.fromDiflist $ .t1:.t2 :-
	same .t1 .t2 ! #
list.fromDiflist (.h, .remains) (.h, .r):.t :-
	list.fromDiflist .remains .r:.t #

list.permutation $ $ #
list.permutation .list (.head, .tail) :-
	list.remove .list .head .remains,
	list.permutation .remains .tail #

list.unique .list0 .list1 :-
	mergeSort .list0 .sorted,
	list.uniqueSorted .sorted .list1 #

list.uniqueSorted $ $ #
list.uniqueSorted (.e, .e, .list0) (.e, .list1) :- !
	list.uniqueSorted .list0 .list1 #
list.uniqueSorted (.e, .list0) (.e, .list1) :-
	list.uniqueSorted .list0 .list1 #

	-- Merge lists, do not duplicate
list.merge $ .list .list :- ! #
list.merge (.head, .tail) .right .merge :-
	list.member .right .head !
	list.merge .tail .right .merge #
list.merge (.head, .tail) .right (.head, .remain) :-
	list.merge .tail .right .remain #

list.sortAndMerge .list .list1 :-
	list.sort .list .sorted,
	mergeSorted .sorted .list1 #

mergeSorted $ $ :- ! #
mergeSorted (.elem, .elem, .remains) .ret :- !
	mergeSorted (.elem, .remains) .ret #
mergeSorted (.elem, .remains) (.elem, .ret) :-
	mergeSorted .remains .ret #

list.flatten $ $ :- ! #
list.flatten (.head, .tail) (.list) :-
	list.flatten .head .flattenedHead,
	list.flatten .tail .flattenedTail,
	list.append .flattenedHead .flattenedTail .list ! #
list.flatten .elem (.elem,) #

list.tuple .list .tuple :-
	io.order .list:.tuple (list.length .list .len, length .tuple .len),
	mapTupleWithListToEnd .tuple 0 .len .list $ #

	-- Length must be given
mapTupleWithListToEnd . .n .n .end .end :- ! #
mapTupleWithListToEnd .tuple .n .len (.head, .tail) .end :-
	nth .tuple .n .head,
	let .n1 (.n + 1),
	mapTupleWithListToEnd .tuple .n1 .len .tail .end #

	-- Longest Common Subsequence
list.lcs $ . $ :- ! #
list.lcs . $ $ :- ! #
list.lcs (.common, .remains1) (.common, .remains2) (.common, .lcs) :-
	lcs.once .remains1 .remains2 .lcs ! #
list.lcs (.head1, .remains1) (.head2, .remains2) .lcs :-
	lcs.once (.head1, .remains1) .remains2 .lcs1,
	lcs.once .remains1 (.head2, .remains2) .lcs2,
	list.length .lcs1 .len1, list.length .lcs2 .len2,
	if (.len1 > .len2) then (
		.lcs = .lcs1
	) else (
		.lcs = .lcs2
	) #

lcs.once .a .b .lcs :-
	get PROVEDs .proveds; .proveds = $ !
	list.member .proveds (LCS .a .b .lcs)
	;
	list.lcs .a .b .lcs,
	set PROVEDs (LCS .a .b .lcs, .proveds) ! #


-- Merge Sort Implementation --

list.sort .list .ret :-
	mergeSort .list .ret #

mergeSort $ $ :- ! #
mergeSort (.e,) (.e,) :- ! #
mergeSort .list .ret :-
	mergeSort.split .list .l1 .l2,
	mergeSort .l1 .sorted1,
	mergeSort .l2 .sorted2,
	mergeSort.ordered .sorted1 .sorted2 .ret ! #

mergeSort.split $ $ $ #
mergeSort.split (.e,) (.e,) $ #
mergeSort.split (.e1, .e2, .remains) (.e1, .l1) (.e2, .l2) :-
	mergeSort.split .remains .l1 .l2 #

mergeSort.ordered $ .e .e #
mergeSort.ordered .e $ .e #
mergeSort.ordered (.e1, .r1) (.e2, .r2) (.e, .remains) :-
	if (compare .e1 .e2) then (
		.e = .e1, mergeSort.ordered .r1 (.e2, .r2) .remains
	) else (
		.e = .e2, mergeSort.ordered (.e1, .r1) .r2 .remains
	) #


-- Difference List --

diflist.add (.item, .lt):.lt .item #

diflist.length .t1:.t2 0 :- same .t1 .t2 ! #
diflist.length (.h, .r):.t .n1 :-
	diflist.length .r:.t .n,
	let .n1 (.n + 1) #

diflist.duplicate .c:.ct .d:.d :- same .c .ct ! #
diflist.duplicate (.h, .cr):.ct (.h, .dr):.dt :-
	diflist.duplicate .cr:.ct .dr:.dt #

diflist.tuple .c:.ct .tuple :-
	diflist.length .c:.ct .len,
	length .tuple .len,
	mapTupleWithListToEnd .tuple 0 .len .c . #


-- Open Lists --

openList.tail (.t, .u) .t :- free .u ! #
openList.tail (., .remains) .t :- openList.tail .remains .t #

openList.append .tail .app :-
	list.append .app . .ext ! openList.extend .tail .ext #

openList.extend .tail .ext :- free .tail ! .tail = .ext #
openList.extend (., .remains) .ext :- openList.extend .remains .ext #

	-- Makes it be bounded; becomes a normal closed-list
openList.terminate .list :- openList.extend .list $ #

openList.duplicate .l . :- free .l ! #
openList.duplicate (.h, .r) (.h, .r1) :- openList.duplicate .r .r1 #
